package lz.firstinterview;

public class BinaryTree {

    /**
     * 生成n层的二叉树，递归调用
     * @param n
     */
    public Node createBinaryTree(int n) {
        Node<String> root = new Node();
        root.setData("root");
        createBinaryNode(root, n-1);
        return root;
    }

    private void createBinaryNode(Node<String> parent, int n) {
        if(n==0) {
            return;
        }
        Node<String> left = new Node();
        parent.setLeft(left);
        left.setParent(parent);
        left.setData(parent.getData()+"-left"+"-"+n);
        Node<String> right = new Node();
        parent.setRight(right);
        right.setData(parent.getData()+"-right"+"-"+n);
        right.setParent(parent);
        createBinaryNode(left, n-1);
        createBinaryNode(right, n-1);
    }

    /**
     * 前序遍历
     * @param root
     */
    public void traversePreorder(Node<String> root) {
        if(root==null) {
            return;
        }
        //访问根结点
        System.out.println(root.getData());
        //访问左子树
        traversePreorder(root.getLeft());
        //访问右子树
        traversePreorder(root.getRight());
        return;
    }

    public void traversePreorder(Node<String> root, int n) {
        if(root==null) {
            return;
        }
        String stepSign = "-";
        //访问根结点
        System.out.println(stepSign.repeat(n)+root.getData());
        int stepNum = n+1;
        //访问左子树
        traversePreorder(root.getLeft(),  stepNum);
        //访问右子树
        traversePreorder(root.getRight(),  stepNum);
        return;
    }

    /**
     * 中序遍历
     * @param root
     */
    public void traverseInorder(Node<String> root) {
        if(root==null) {
            return;
        }
        //访问左子树
        traverseInorder(root.getLeft());
        //访问根结点
        System.out.println(root.getData());
        //访问右子树
        traverseInorder(root.getRight());
        return;
    }

    /**
     * 后序遍历
     * @param root
     */
    public void traversePostorder(Node<String> root) {
        if(root==null) {
            return;
        }
        //访问左子树
        traversePostorder(root.getLeft());
        //访问右子树
        traversePostorder(root.getRight());
        //访问根结点
        System.out.println(root.getData());
        return;
    }




    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        Node<String> root = binaryTree.createBinaryTree(3);
        System.out.println();
        //binaryTree.traversePreorder(root);
        //binaryTree.traverseInorder(root);
        binaryTree.traversePostorder(root);

    }
}
